#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:6031)

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x)
    {
        ListNode* cur = pHead;
        ListNode* lesslist, * lesstail, * biglist, * bigtail;
        lesstail = (ListNode*)malloc(sizeof(struct ListNode));
        lesslist = lesstail;

        bigtail = (ListNode*)malloc(sizeof(struct ListNode));
        biglist = bigtail;
        while (cur)
        {
            if (cur->val < x)
            {
                lesslist->next = cur;
                lesslist = lesslist->next;
            }
            else
            {
                biglist->next = cur;
                biglist = biglist->next;
            }
            cur = cur->next;
        }
        biglist->next = NULL;
        lesslist->next = bigtail->next;
        pHead = lesstail->next;

        free(lesstail);
        free(bigtail);
        return pHead;

    }
};